package zhengqc.search;

public class BinarySearch<E extends Comparable<E>> extends Search<E> {
    public enum BinarySearchType {
        IterativeSearch,
        RecursiveSearch,
        UpperSearch,
        LowerSearch,
    }
    public BinarySearch() {
        this.searchName = "BinarySearch";
    }
    public int search(E[] data, E target, BinarySearchType binarySearchType) {
        switch (binarySearchType) {
            case RecursiveSearch:
                return recursiveSearch(data, 0, data.length-1, target);
            case LowerSearch:
                return lowerSearch(data, target);
            case UpperSearch:
                return upperSearch(data, target);
            default:
            case IterativeSearch:
                return iterativeSearch(data, 0, data.length-1, target);
        }
    }

    @Override
    public int search(E[] data, E target) {
        return this.search(data, target, BinarySearchType.IterativeSearch);
    }

//    private int iterativeSearch(E[] data, int left, int right, E target) {
//        // 循环不变量: 在 data[left, right) 的范围内查找 target
//        while (left < right) {
//            int mid = left + (right-left) / 2;
//            if (data[mid].compareTo(target) < 0) {
//                left = mid + 1;     // 继续在 data[mid+1, right) 的范围里寻找解
//            } else if (data[mid].compareTo(target) > 0) {
//                right = mid;    // 继续在 data[left, mid) 的范围里寻找解
//            } else {
//                return mid;
//            }
//        }
//        return -1;
//    }
    private int iterativeSearch(E[] data, int left, int right, E target) {
        // 循环不变量: 在 data[left, right] 的范围内查找 target
        while (left <= right) {
            int mid = left + (right-left) / 2;
            if (data[mid].compareTo(target) < 0) {
                left = mid + 1;
            } else if (data[mid].compareTo(target) > 0) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    private int recursiveSearch(E[] data, int left, int right, E target) {
        if (left > right) return -1;
        int mid = left + (right-left) / 2;

        if (data[mid].compareTo(target) < 0) {
            return recursiveSearch(data, mid+1, right, target);
        }
        if (data[mid].compareTo(target) > 0) {
            return recursiveSearch(data, left, mid-1, target);
        }
        return mid;
    }
    /* 查找大于 target 的最小索引值; 搜索范围 array[left, right], left = 0, right = array.length */
    public int upperSearch(E[] data, E target) {
        int left = 0, right = data.length;
        // 循环不变量: 在 data[left, right] 的范围内查找 target
        while (left < right) {
            int mid = left + (right-left) / 2;      // 默认向下取整
            if (data[mid].compareTo(target) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    /* 查找小于 target 的最大索引值; 搜索范围 array[left, right], left = -1, right = array.length-1 */
    public int lowerSearch(E[] data, E target) {
        int left = -1, right = data.length-1;
        // 循环不变量: 在 data[left, right] 的范围内查找 target
        while (left < right) {
            int mid = left + (right-left+1) / 2; // 注意条件: 向上取整
            if (data[mid].compareTo(target) >= 0) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}
